Embodiments of the present invention relate to a concept for encoding data defining coded orientations representing a reorientation of an object based on spatio-temporal data representing a time series of orientations of the object.
Traditional location systems rely on spatio-temporal data of located objects. Spatio-temporal data may be used for visualizing scenes, e.g. for an operator that directs bus drivers to the next free parking slot. Or for an autonomic monitoring system that checks if all objects are within a certain boundary and that gives an alarm if an object reaches into a dangerous area, for example, if a human reaches a pressing plant. But spatio-temporal representations reach their limits if more information on the object itself is necessitated, in particular, if the behavior is important. A good example is a soccer match, where a viewer wants to automatically detect an event, such as that a player is performing a sprint or that the ball is kicked. Just from spatio-temporal data such events can hardly be detected.
Spatio-temporal data is also not amenable to matching of trajectories. The reason is that trajectories have to be rotated, translated, and scaled, before a similarity can be detected. Also, coordinates are not intuitive for describing a trajectory. For example, a set of coordinates and time stamps along a synthetic trajectory have to be defined.
Current research on trajectory representation is mainly targeted to queries in databases, i.e. to search for similar stored trajectories or for time series with some specific characteristics. In the article “Similarity search in trajectory databases”, N. Pelekis, I. Kopanakis, G. Marketos, I. Ntoutsi, G. Andrienko, and Y. Theodoridis introduce a set of similarity metrics for querying trajectories, that not only find similar trajectories but that also support trajectory clustering and mining tasks. Their distance operator, called Locality In-between Polylines (LIP), calculates the crossing area of two trajectories. Further, operators for time-aware spatio-temporal trajectory similarity search are defined. The underlying dataset consists of a classical spatio-temporal database.
In the article “Modeling of moving objects in a video database”, J. Li, M. Ozsu, and D. Szafron introduce a trajectory representation of a sequence of motions, which are expressed on a series of displacement, moving direction and time interval. The moving direction can be one of the eight cardinal points (NT, NE, ET, SE, ST, SW, WT, NW). Trajectories are compared by a moving spatio-temporal relationship (mst-relation), which is a set of topological relations, directional relations and a time interval. This approach results in an abstraction and human readability of the spatio-temporal data, but does not allow a detailed reconstruction of the trajectory.
A grouping algorithm is shown in the article “Trajectory representation in location-based services: prRBLems & solution” by Meratnia and de By to select regions in trajectories where the velocity or acceleration is constant. The trajectories are segmented by break points and represented by functions that are fitted into the resulting segments. The representation abstracts the trajectory in a very compact way, but does not allow a direct online approach, because a set of samples is needed for grouping. This introduces latency that is worth for online applications in Real-Time Location Systems (RTLSs).
In the article “Motion-alert: Automatic anomaly detection in massive moving objects”, X. Li, J. Han, and S. Kim present a motion classifier that is based on movement features, called motifs. An object's path consists of a sequence of motif expressions, which are an abstraction of the underlying trajectory segment, at a given time and location, for example, “Right-Turn 3 am, 17”. This abstraction level is suitable for classification task, but a detailed reconstruction of the original trajectory is not possible.
A similar approach is shown by A. Kojima, M. Izumi, T. Tamura, and K. Fukunaga in the article “Generating natural language description of human behavior from video images”. The motion is described by a more human language inspired expression, with the objective to explain the object's behavior. The behavior is estimated by evaluating the pose and position in relation to surrounding objects. The main focus is to generate a human readable text, which is created by a machine translation technique. Since the objective is to maximize the readability for humans, the resulting text is not suitable for detail trajectory analysis.
A Movement Pattern String (MPS) is proposed by L. Chen, M. T. Özsu, and V. Oria in “Symbolic representation and retrieval of moving object trajectories” to represent trajectories as a string of symbols. The symbols are selected by calculating the movement direction and movement distance ratio for every sampling point and choosing the corresponding symbol from a quantization map. The similarity of two trajectory strings is determined by calculating the Edit Distance on Real Sequence (EDR), which is a derivation of the Levenshtein distance. The distance ratio needs to know the whole trajectory size that prohibit an online translation. Also the readability of the symbol string is less suitable for humans.
A resampling based concept is described in the article “A new perspective on trajectory compression techniques” from N. Meratnia and R. A. de By. A further resampling based concept is described in the article “Sampling trajectory streams with spatiotemporal criteria” from M. Potamias, K. Patroumpas, and T. Sellis. Another resampling based concept is described in the article “Compressing trajectory data of moving objects” from M. Potamias.
In the article “Semantic trajectory compression” from F. Schmid, K.-F. Richter, and P. Laube, a semantic based concept is described.
Y. Xu and W.-C. Lee describe in their article “Delay-tolerant compression for object tracking sensor network” a segmentation and approximation based concept. Thereby, trajectories are segmented and approximated via functions. Thereby, the segmentation necessitates an amount of points resulting in a high latency.
Further convention is known from the article “Spatio-temporal data reduction with deterministic error” from H. Cao, O. Wolfson, and G. Trajcevski; the article “On the effect of trajectory compression in spatiotemporal querying” from E. Fretznos, and Y. Theodoridis; the article “Space-efficient online approximation of time series data: Streams, amnesia, and out of order” from S. Gandhi, L. Foschini and S. Suri; the article “Compressing spatio-temporal trajectories” from J. Gudmundsson, J. Katajainen, D. Merrick, C. Ong, and T. Wolle; and the article “Lossy compression of tpc data and trajectory tracking efficiency for the alice experiment” from A. Nicolaucig, M. Ivanov and M. Mattavelli.
Furthermore, when transmitting location data of a moving object at run time, as it is the case in real time location systems (RTLSs), large amounts of data or data quantities occur at high sample rates or with a high number of transmitted location data. For long time storage or transmission to mobile terminal devices, reducing the amount of data saves memory space or bandwidth, respectively. Since data mostly have to be processed in real time during transmission, classical compression techniques cannot be used here. The data have to be compressed and decompressed at run time without introducing process-induced latencies.